I. Technical Field
This disclosure relates generally to apparatus and methods for corner and/or interest point detection in images, and more particularly to a method to determine the number of corners and/or interest points in an image.
II. Background
The Features from Accelerated Segment Test (“FAST”) algorithm is a commonly used method of finding corners in an image in computer vision systems. Corners are points where two or more edges intersect or whose immediate neighborhood includes two or more dominant edges with different directions. In general, algorithms such as FAST detect interest points in an image, which have well-defined positions. Therefore, while interest points may be corners, they include isolated points with a local intensity maximum or minimum. As used herein, the term corner encompasses interest points.
The FAST algorithm is publically available as code from Edward Rosten, Tom Drummond and Los Alamos National Laboratory. The FAST algorithm scans through every pixel of an image in order to find pixels that represent corners. While easy to understand, the FAST algorithm requires a large number of iterative computations. Moreover, the FAST algorithm fails to scale well to a paralleled architecture, which makes it difficult to implement on an ASIC or SIMD processor.
FIG. 1 shows exemplary pixel 120 on surrounding ring 110 of M pixels. Ring 110 overlaying the pixel grid highlights the M pixels that comprise ring 110 about center pixel 120. Exemplary center pixel 120 is a corner if and only if it is brighter or darker than N consecutive pixels on surrounding ring 110 of M pixels. The values of N and M are design parameters, which are normally N=9 to 12 for M=16.
FIG. 2 shows exemplary center pixel 120 with intensity x and pixels on surrounding circle 110 with various intensities yi. As shown in FIG. 2, yi denotes the intensity of the pixel at position i on circle 110. Pixels are numbered sequentially i=0, 1, 2 . . . M−1, about the surrounding ring 110 and have intensities y1, . . . , yM−1. A first pixel at position 0 has a first intensity y0. The pixels y0, y1, . . . , yM−1 complete the surrounding ring 110 of M pixels.
FIGS. 3 and 4 show a ring 110 of M pixels having various intensities about center pixel 120. Pixels comprising ring 110 may be computed, for example, by using well-known computer graphics techniques, such as a midpoint circle algorithm or the Bresenham's circle algorithm, which determine the points needed for drawing a circle.
More formally, let A be any set of the indexes of N consecutive pixels on the ring of M pixels. The FAST algorithm detects corners using the rule:
                    center        ⁢                                  ⁢        pixel        ⁢                  {                                                                      bright                  ⁢                                                                          ⁢                  corner                                                                              if                  ⁢                                                                          [                                                                                    (                                                  x                          -                                                      y                            i                                                                          )                                            >                      t                                        ,                                          ∀                                              i                        ∈                        A                                                              ,                                          ∃                      A                                                        ]                                                                                                      dark                  ⁢                                                                          ⁢                  corner                                                                              if                  ⁢                                                                          [                                                                                    (                                                                              y                            i                                                    -                          x                                                )                                            >                      t                                        ,                                          ∀                                              i                        ∈                        A                                                              ,                                          ∃                      A                                                        ]                                                                                                      not                  ⁢                                                                          ⁢                  a                  ⁢                                                                          ⁢                  corner                                                            otherwise                                                                        (        1        )            where t is a predetermined threshold to filter out weak corners. For each detected corner pixel, the FAST algorithm defines a score, which is the maximum threshold t for the pixel to remain a corner. The score measures the “cornerness” of the pixel or the degree to which the pixel may be considered a corner relative to other pixels, and may be used to further filter out weaker corners when too many corners are found. That is, the FAST algorithm may be iteratively executed to find a threshold t that reduces a number of corners to a desired number of corners.
The FAST algorithm finds corners via a decision tree. Each tree node may be viewed as a “compare” gate that tests for either (x−yi)>t or (yi−x)>t. In most cases, each tree node leads to either another tree node or a leaf node. A leaf node represents the final decision, which is either a corner is affirmed or a corner is not found at a particular center pixel. The decision tree is designed using empirical data so that the average traversal depth is minimal. After a corner is found, a binary search is performed by varying t iteratively in order to find the score threshold.
There are a few drawbacks to the above FAST algorithm. First, the computational complexity depends on the average traversal depth of the decision tree. Second, because the decision tree is designed using empirical data, it may not be optimal for all possible data sets. Third, the decision tree is a large tree, so it takes a large amount of software code space or a large number of hardware gates to implement. Fourth, when implemented in software, each tree node is mapped to a simple comparison test followed by a conditional branch, which incurs a large number of CPU cycle overhead on deeply pipelined processors. Fifth, all the inefficiencies are further compounded by the iterative nature of the algorithm, since multiple iterations mean the decision tree will be traversed more than one time.
Detecting corners is important in many computer vision applications, like motion detection, object recognition and tracking, object navigation, image stitching, 3D reconstruction, etc. The large variety of application areas make resource and time efficient implementations of corner detection methods desirable.
Therefore, a method of performing the FAST corner detection that reduces complexity and processing is desired.